#define _CRT_SECURE_NO_WARNINGS 1

#include"sort.h"

void swap(int* a, int* b)
{
	int tmp =*a;
	*a = *b;
	*b = tmp;
}

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
//  4  2  6  8  5  9 

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		bool flag = false;
		for (int j = 0; j < n-i-1; j++)
		{
			if (a[j] > a[j + 1])
				swap(&a[j],&a[j + 1]);
			flag = true;
		}

		if (flag == false) break;

	}
}

//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };
//            2  3 
//            2  3  6  4  8  
void InsertSort(int* a, int n)
{
	// [0, end] end+1
	for (int i = 0; i < n - 1; ++i)
	{
		int key = a[i + 1];
		int j = i;
		while (j>=0&&a[j]>key)
		{
			a[j + 1] = a[j--];
		}

		a[j + 1] = key;
	}
}
void Insert_Sort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i + 1;
		for (int j = i; j >= 0; j--)
		{
			
			if (a[end] < a[j]) {
				swap(&a[end], &a[j]);
					end--;
			}
			else break;
		}
	}
}

//
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap>1)
	{
		gap = gap/3+1;
		for (int i = 0; i < n - gap; i+=gap)
		{
			int key = a[i + gap];
			int j = i;
			while (j >= 0 && a[j] > key)
			{
				a[j + gap] = a[j];
				j -=gap;
			}

			a[j + gap] = key;
		}

	}
}



// 选择排序
void SelectSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int min_idx = i;
		for (int j = i+1; j < n; j++)
		{
			if (a[j] < a[min_idx])
			{
				min_idx = j;
			}
		}
		int tmp = a[i];
		a[i] = a[min_idx];
		a[min_idx] = tmp;

	}
}


// 堆排序
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = parent*2 + 1;
	while (child<n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
			child++;

		if (a[child] > a[parent])
		{
			int tmp = a[parent];
			a[parent] = a[child];
			a[child] = tmp;
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	//构建大堆
	for (int i = n / 2 - 1; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}

	for (int end = n - 1; end > 0; end--)
	{
		int tmp = a[0];
		a[0] = a[end];
		a[end] = tmp;
		AdjustDwon(a, end, 0);
	}
}

